题解 CF1175E 【Minimal Segment Cover】

发表于 | 更新于

$Description$

给出$n$个形如$[l,r]$的线段。$m$次询问，每次询问区间$[x,y],$问至少选出几条线段，使得区间$[x,y]$的任何一个部位都被至少一条线段覆盖。

$Solution$

考虑贪心，首先设询问区间为$[x,y],$你选的所有$[l,r]$中最左边的一个$l$必然$\leqslant x($有且仅有一个$),$所以对于这个区间，它对答案的贡献取决于它的$r,$所以我们希望它在满足$l\leqslant x$的情况下$~r$更大，那么取完第一个这个问题就变成了一个$[r+1,y]$的子问题了，直到选取的$r\geqslant y$为止。

但是这个复杂度是$O(nm),$考虑倍增，每次向右跳$2^i$条线段，那么复杂度就变成$O(n~log~m)$了。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 560000
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int n,m,to[N],f[N][22],mx;
signed main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i){
        int x=read(),y=read();
        to[x]=max(to[x],y); 
        mx=max(mx,y); 
    }
    for (int i=0;i<=mx;++i)f[i][0]=to[i]=max(to[i],to[i-1]);
    for (int j=1;j<=20;++j)
        for (int i=0;i<=mx;++i)
            f[i][j]=f[f[i][j-1]][j-1];
    while (m--){
        int x=read(),y=read(),ans=0;
        for (int i=20;i>=0;--i){
            if (f[x][i]<y&&f[x][i]>x)
                x=f[x][i],ans+=(1<<i);
        }
        if (to[x]>=y)printf("%d\n",ans+1);
        else puts("-1");
    }
    return 0;
}